package two.stack_queue;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 滑动窗口最大值-单调队列模板
 * nums = [1,3,-1,-3,5,3,6,7], k = 3
 * 时间复杂度：O(n）
 * 思路：单调队列（和中间的数值有关）
 */
public class MaxSlidingWindow {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] answer = new int[nums.length - k + 1];//结果
        //双端队列存下标（下标代表时间）
        Deque<Integer> dq = new LinkedList<>(); //单调队列（维护一个单调递减的序列）
        for(int i = 0; i < nums.length; i++){
            //保证队头的合法性
            while(!dq.isEmpty() && dq.getFirst() <= (i - k)) dq.removeFirst();
            //维护队列的单调性，插入新选项
            while (!dq.isEmpty() && nums[dq.getLast()] <= nums[i]) dq.removeLast();
            dq.addLast(i);
            //取对头更新答案
            if(i >= k - 1) answer[i - (k - 1)] = nums[dq.getFirst()];
        }
        return answer;
    }
}
